package Upr;

import java.util.Arrays;

public class exer {

	public static void main(String[] args) 
	{
		int[] number1 = {546,645,8,5,54,87,45,86,7564,654,8,655,564,564,9};
		int[] number = {43,65,23,65,32,75,32,54,1,5,2,97};
		int[] num = {1,2,3,5,6,7,8,9,6,4,2,1,2,5,7,8,4};
		int n = 5;
		
		for(int i = 1; i <= n; i++)
		{
			printLine(1, i);
		}
		
		for(int i = n - 1; i >= 0; i--)
		{
			printLine(1, i);
			
		}
		
		System.out.println(Arrays.toString(number));

		number = selectionSort(number);
		System.out.println(Arrays.toString(number));

		bubbleSort(number);
		
		System.out.println(Arrays.toString(num));
		countingSort(num);
		
		System.out.println(Arrays.toString(number1));
		radixSort(number1);
		buildHeap(number);
		sortHeap(number);
	}
	
	public static void printLine (int start, int end)
	{
		for (int i = start; i <= end; i++)
		{
			System.out.print(" " + i);
		}
		
		System.out.println();
		
	}
	
	public static int[] selectionSort (int[] number)
	{
		
		for(int i = 0; i < number.length; i++)
		{
			for(int j = 0; j < number.length; j++)
			if(number[i] < number[j])
			{
				int t = number[i];
				number[i] = number[j];
				number[j] = t;
			}

		}
		return number;
	}

	public static void bubbleSort( int[] number)
	{

		boolean flag = true;
		 while ( flag )
	     {
	            flag = false;    //set flag to false awaiting a possible swap
	            for(int i = 0;  i < number.length-1;  i++ )
	            {
	                   if ( number[ i ] < number[i+1] )   // change to > for ascending sort
	                   {
	                           int temp = number[ i ];                //swap elements
	                           number[ i ] = number[ i+1 ];
	                           number[ i+1 ] = temp;
	                          flag = true;              //shows a swap occurred  
	                  } 
	            } 
	      }
			System.out.println(Arrays.toString(number));

	}
	
	public static void countingSort( int[] num)
	{
		
		int[] helper = new int [num.length];
		int[] helpInd = new int [10];
		int ind = 0;
		
		for(int i = 0; i < num.length; i++)
		{
			helpInd[num[i]]++;
		}
		
		for(int i = 0; i < helpInd.length; i++)
		{
			while(helpInd[i] > 0)
			{
				helper[ind] = i;
				ind++;
				
				helpInd[i]--;
	
			}
			
		}
		
		System.out.println(Arrays.toString(helper));
		
	}

	public static void radixSort (int[] number1)
	{
		
		int max = 0;
		
		for(int i = 0; i < number1.length; i++)
		{
			if(number1[i] > max)
			{
				max = number1[i];
			}
			
		}
		
		int devider = 1;
		int[] save = new int [number1.length];
		
		while(max / devider > 0)
		{
			int[] helpInd = new int [10];

			for(int i = 0; i < number1.length; i++)
			{
				int lastDigit = number1[i]/devider%10;
				helpInd[lastDigit]++;
			}

			for(int i = 1; i < helpInd.length; i++)
			{
				helpInd[i] += helpInd[i - 1];
			}
			
			System.out.println(Arrays.toString(helpInd));
			for(int i = number1.length - 1; i >= 0; i--)
			{
				int lastDigit = number1[i] / devider % 10;
				int position = --helpInd[lastDigit];
				save[position] = number1[i];
				
			}
			
			for(int i = 0; i < number1.length; i ++)
			{
				number1[i] = save[i];
			}
			System.out.println(Arrays.toString(number1));

			devider *= 10;

		}

		
	}

	public static void buildHeap (int[] number)
	{
		for(int i = 0; i < number.length; i++)
		{
			int nodeIndex = i;
			
			while ( nodeIndex != 0)
			{
				int parentInd = (nodeIndex - 1) / 2;
				if (number[parentInd] < number[nodeIndex])
				{
					int t = number[parentInd];
					number[parentInd] = number[nodeIndex];
					number[nodeIndex] = t;
				}
				nodeIndex = parentInd;
				
			}
			
		}
		
		System.out.println(Arrays.toString(number) + "buildHeap");
		
	}

	public static void sortHeap (int[] number)
	{
		buildHeap(number);
		
		for(int i = 0; i < number.length; i++)
		{
			
			int heapLength = number.length - 1 - i;
			swap(number, 0, heapLength);
			
			int parentInd = 0;
			
			while(true)
			{
				int left = parentInd*2 + 1;
				int right = parentInd*2 + 2;
				if(left >= heapLength)
				{
					break;
				}
				else
					if(right >= heapLength)
					{
						if(number[parentInd] < number[left])
						{
							swap(number, parentInd, left);
						}
						break;
					}
					else
					{
						if(number[left] > number[right])
						{
							if(number[left] > number[parentInd])
							{
								swap(number, left, parentInd);
							}
							parentInd = left;
						}
						else
						{
							if(number[right] > number[parentInd])
							{
								swap(number, right, parentInd);
							}
							parentInd = right;
						}
					}
				
			}
		}
		
		System.out.println(Arrays.toString(number));
		
		
		
	}

	private static void swap(int[] number, int i, int j)
	{
		int temp = number[i];
		number[i] = number[j];
		number[j] = temp;
		
	}
	
	
}
